def lca_parent(r, n1, n2):
	t = n1
	int n1_depth = 0
	while t != r:
		if t == n2:
			return n2
		n1_depth++
		t = t.parent

	# PRE: n2 is not the ancestor of the n1
	# PRE: n1_depth is the depth of the n1

	t = n2
	int n2_depth = 0
	while t != r:
		if t == n1:
			return n1
		n2_depth++
		t = t.parent

	# PRE: n1 is not the ancestor of the n2
	# PRE: n2_depth is the depth of the n2

	if n1_depth > n2_depth:
		t = n1
		n1 = n2
		n2 = t

	# PRE: n1_depth <= n2_depth
	while n1_depth > 0:
		n2 = n2.parent
		n2_depth--
		# either n1_depth < n2_depth OR n1_depth == n2_depth
		if n1_depth == n2_depth:
			n1 = n1.parent
			n1_depth--

		if n1 == n2: #LCA found
			return n1


	return None


		


